///| 大整数类型。使用数组存储数字的各个位，
/// 采用小端序存储，即低位在前，高位在后，
/// 每个元素存储一个32位的数字
/// 
pub struct BigInt {
  /// 数字的各个位，采用小端序
  digits : Array[UInt]
  /// 符号位，true表示负数，false表示正数
  negative : Bool
}

///| 创建一个值为0的大整数
pub fn BigInt::zero() -> BigInt {
  { digits: [0U], negative: false }
}

///| 创建一个值为1的大整数
pub fn BigInt::one() -> BigInt {
  { digits: [1U], negative: false }
}

///| 从整数创建大整数
pub fn BigInt::from_int(value : Int) -> BigInt {
  if value == 0 {
    return BigInt::zero()
  }
  let negative = value < 0
  let abs_value = if negative { -value } else { value }
  { digits: [abs_value.reinterpret_as_uint()], negative }
}

///| Define a custom error type for BigInt parsing errors
suberror ParseError String

///| 从字符串创建大整数
pub fn BigInt::from_string(s : String) -> BigInt raise ParseError {
  if s.length() == 0 {
    raise ParseError("Empty string")
  }
  
  let mut start = 0
  let negative = s.charcode_at(0) == '-'.to_int()
  if negative || s.charcode_at(0) == '+'.to_int() {
    start = 1
  }
  
  if start >= s.length() {
    raise ParseError("Invalid number format")
  }
  
  let mut result = BigInt::zero()
  let base = BigInt::from_int(10)
  
  for i = start; i < s.length(); i = i + 1 {
    let char_code = s.charcode_at(i)
    if char_code < '0'.to_int() || char_code > '9'.to_int() {
      raise ParseError("Invalid digit: " + char_code.to_char().to_string())
    }
    let digit = char_code - '0'.to_int()
    result = result.op_mul(base).op_add(BigInt::from_int(digit))
  }
  
  let final_result = if negative && not(result.is_zero()) {
    { digits: result.digits, negative: true }
  } else {
    result
  }
  
  final_result
}

///| 检查是否为零
pub fn is_zero(self : BigInt) -> Bool {
  self.digits.length() == 1 && self.digits[0] == 0
}

///| 检查是否为正数
pub fn is_positive(self : BigInt) -> Bool {
  not(self.negative) && not(self.is_zero())
}

///| 检查是否为负数
pub fn is_negative(self : BigInt) -> Bool {
  self.negative
}

///| 获取绝对值
pub fn abs(self : BigInt) -> BigInt {
  { digits: self.digits.copy(), negative: false }
}

///| 取负值
pub fn negate(self : BigInt) -> BigInt {
  if self.is_zero() {
    return self
  }
  { digits: self.digits.copy(), negative: not(self.negative) }
}

///| 移除前导零
fn normalize(self : BigInt) -> BigInt {
  let mut len = self.digits.length()
  while len > 1 && self.digits[len - 1] == 0 {
    len = len - 1
  }
  
  if len == self.digits.length() {
    return self
  }
  
  let new_digits = Array::make(len, 0U)
  for i = 0; i < len; i = i + 1 {
    new_digits[i] = self.digits[i]
  }
  
  { digits: new_digits, negative: self.negative && not(len == 1 && new_digits[0] == 0) }
}

///| 比较两个大整数的绝对值
/// 返回值：`-1` 表示 `self < other`，`0` 表示相等，`1` 表示 self > other
fn compare_abs(self : BigInt, other : BigInt) -> Int {
  if self.digits.length() != other.digits.length() {
    return if self.digits.length() > other.digits.length() { 1 } else { -1 }
  }
  
  for i = self.digits.length() - 1; i >= 0; i = i - 1 {
    if self.digits[i] != other.digits[i] {
      return if self.digits[i] > other.digits[i] { 1 } else { -1 }
    }
  }
  
  0
}

/// 比较两个大整数
pub fn compare(self : BigInt, other : BigInt) -> Int {
  if self.negative != other.negative {
    return if self.negative { -1 } else { 1 }
  }
  
  let abs_cmp = self.compare_abs(other)
  if self.negative { -abs_cmp } else { abs_cmp }
}

/// 相等比较
pub fn op_equal(self : BigInt, other : BigInt) -> Bool {
  self.compare(other) == 0
}

/// 小于比较
pub fn op_less_than(self : BigInt, other : BigInt) -> Bool {
  self.compare(other) < 0
}

/// 小于等于比较
pub fn op_less_equal(self : BigInt, other : BigInt) -> Bool {
  self.compare(other) <= 0
}

/// 大于比较
pub fn op_greater_than(self : BigInt, other : BigInt) -> Bool {
  self.compare(other) > 0
}

/// 大于等于比较
pub fn op_greater_equal(self : BigInt, other : BigInt) -> Bool {
  self.compare(other) >= 0
}

/// 转换为字符串
pub fn to_string(self : BigInt) -> String {
  if self.is_zero() {
    return "0"
  }
  
  let mut result = self.abs()
  let digits : Array[Int] = []
  let ten = BigInt::from_int(10)
  
  while not(result.is_zero()) {
    let (quotient, remainder) = result.div_mod(ten)
    digits.push(remainder.digits[0].reinterpret_as_int())
    result = quotient
  }
  
  let mut s = ""
  if self.negative {
    s = s + "-"
  }
  
  for i = digits.length() - 1; i >= 0; i = i - 1 {
    s = s + digits[i].to_string()
  }
  
  s
}
